package leetcode.N1_N100;

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/19 5:47 下午
 */
public class N93 {

    public static void main(String[] args) {
        System.out.println(restoreIpAddresses("00010"));
    }

    static List<String> result = new ArrayList<>();

    public static List<String> restoreIpAddresses(String s) {
        result.clear();
        choose("", s.toCharArray(), 0, s.length() - 1, 1);
        return result;
    }

    private static void choose(String last, char[] s, int start, int end, int floor) {
        int length = end - start;
        if (length < 0) {
            return;
        }
        // 如果是最后一轮 则直接使用剩下的数
        if (floor == 4) {
            if (length > 2) {
                // 剩下的数字大于三位 则必定不成立
                return;
            }
            if (s[start] == '0' && start != end) {
                // 剩下的数字大于1位，且首位是0  不符合条件
                return;
            }
            String strVal = String.copyValueOf(s, start, length + 1);
            Integer intVal = Integer.parseInt(strVal);
            if (intVal > 255) {
                return;
            } else {
                result.add(last + intVal);
            }
            // 处理完毕
            return;
        }
        // 其他轮 其实是一样的逻辑
        // 枚举去数方式 1位 2位 小于等于255的三位

        // 1 位 需要满足一个条件 剩余位数大于   4 - floor + 1
        if (!(length + 1 >= 3 - floor + 1)) {
            return;
        }
        choose(last + s[start] + ".", s, start + 1, end, floor + 1);

        // 2位 需要满足两个条件
        // 1-首位不是0, 2-剩余位数大于等于 4 - floor + 2
        if (!(length + 1 >= 3 - floor + 2) || s[start] == '0') {
            return;
        }
        choose(last + s[start] + s[start + 1] + ".", s, start + 2, end, floor + 1);
        // 3位 需要满足三个个条件
        // 1-首位不是0, 2-剩余位数大于等于 4 - floor + 3, 3-数字小于等于255
        if (!(length + 1 >= 3 - floor + 3) || s[start] == '0') {
            return;
        }
        String strVal = String.copyValueOf(s, start, 3);
        Integer intVal = Integer.parseInt(strVal);
        if (intVal > 255) {
            return;
        }
        choose(last + strVal + ".", s, start + 3, end, floor + 1);
    }

}
